package com.example.lettcode._202412._20241219;

import java.util.ArrayList;
import java.util.List;

/*
696. 计数二进制子串
给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：
输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：
输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

提示：
1 <= s.length <= 105
s[i] 为 '0' 或 '1'
 */
public class _696_ji_shu_er_jin_zhi_zi_chuan {

    public static void main(String[] args) {
        String s = "10101";
        System.out.println(countBinarySubstrings3(s));
    }

    /*
        超时
     */
    public static int countBinarySubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        // 统计返回结果的
        int count1 = 0;
        // 统计0或1的个数的
        int count2 = 1;
        int tempCount2 = 1;
        // flag:代表和第一个遍历的char相同值，并且没有间隔其他的值
        boolean flag = true;
        for (int i = 0; i < n; i++) {
            char aChar = chars[i];
            for (int j = i+1; j < n; j++) {
                char jChar = chars[j];
                if (flag && jChar == aChar) {
                    count2++;
                    tempCount2 = count2;
                } else if (jChar != aChar) {
                    count2--;
                    if (count2 == 0) {
                        count1 += tempCount2;
                        i += tempCount2-1;
                        break;
                    }
                    flag = false;
                }
                if (!flag && jChar == aChar) {
                    // 说明是 0010,又遍历到最后一个0了，这种情况下，直接结束
                    break;
                }
            }
            count2 = 1;
            tempCount2 = 1;
            flag = true;
        }
        return count1;
    }

    public static int countBinarySubstrings2(String s) {
        int left = 0, n = s.length();
        char[] chars = s.toCharArray();
        List<Integer> list = new ArrayList<>();
        while (left < n) {
            char aChar = chars[left];
            int count = 0;
            while (left < n && chars[left] == aChar) {
                count++;
                left++;
            }
            list.add(count);
        }

        int ret = 0;
        for (int i = 1; i < list.size(); i++) {
            ret += Math.min(list.get(i), list.get(i-1));
        }
        return ret;
    }

    public static int countBinarySubstrings3(String s) {
        int prev = 0, n = s.length(), last = 0, ret = 0;
        char[] chars = s.toCharArray();
        while (prev < n) {
            char aChar = chars[prev];
            int count = 0;
            while (prev < n && chars[prev] == aChar) {
                count++;
                prev++;
            }
            ret += Math.min(count, last);
            last = count;
        }
        return ret;
    }
}
